// Copyright 2011 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_HEAP_STORE_BUFFER_H_
#define V8_HEAP_STORE_BUFFER_H_

#include "src/allocation.h"
#include "src/base/logging.h"
#include "src/base/platform/platform.h"
#include "src/cancelable-task.h"
#include "src/globals.h"
#include "src/heap/gc-tracer.h"
#include "src/heap/remembered-set.h"
#include "src/heap/slot-set.h"

namespace v8 {
namespace internal {

    // Intermediate buffer that accumulates old-to-new stores from the generated
    // code. Moreover, it stores invalid old-to-new slots with two entries.
    // The first is a tagged address of the start of the invalid range, the second
    // one is the end address of the invalid range or null if there is just one slot
    // that needs to be removed from the remembered set. On buffer overflow the
    // slots are moved to the remembered set.
    // Store buffer entries are always full pointers.
    class StoreBuffer {
    public:
        enum StoreBufferMode { IN_GC,
            NOT_IN_GC };

        static const int kStoreBuffers = 2;
        static const int kStoreBufferSize = Max(static_cast<int>(kMinExpectedOSPageSize / kStoreBuffers),
            1 << (11 + kSystemPointerSizeLog2));
        static const int kStoreBufferMask = kStoreBufferSize - 1;
        static const intptr_t kDeletionTag = 1;

        V8_EXPORT_PRIVATE static int StoreBufferOverflow(Isolate* isolate);

        static void DeleteDuringGarbageCollection(StoreBuffer* store_buffer,
            Address start, Address end);
        static void InsertDuringGarbageCollection(StoreBuffer* store_buffer,
            Address slot);

        static void DeleteDuringRuntime(StoreBuffer* store_buffer, Address start,
            Address end);
        static void InsertDuringRuntime(StoreBuffer* store_buffer, Address slot);

        explicit StoreBuffer(Heap* heap);
        void SetUp();
        void TearDown();

        // Used to add entries from generated code.
        inline Address* top_address() { return reinterpret_cast<Address*>(&top_); }

        // Moves entries from a specific store buffer to the remembered set. This
        // method takes a lock.
        void MoveEntriesToRememberedSet(int index);

        // This method ensures that all used store buffer entries are transferred to
        // the remembered set.
        void MoveAllEntriesToRememberedSet();

        inline bool IsDeletionAddress(Address address) const
        {
            return address & kDeletionTag;
        }

        inline Address MarkDeletionAddress(Address address)
        {
            return address | kDeletionTag;
        }

        inline Address UnmarkDeletionAddress(Address address)
        {
            return address & ~kDeletionTag;
        }

        inline void InsertDeletionIntoStoreBuffer(Address start, Address end);
        inline void InsertIntoStoreBuffer(Address slot);

        void InsertEntry(Address slot)
        {
            // Insertions coming from the GC are directly inserted into the remembered
            // set. Insertions coming from the runtime are added to the store buffer to
            // allow concurrent processing.
            insertion_callback(this, slot);
        }

        // If we only want to delete a single slot, end should be set to null which
        // will be written into the second field. When processing the store buffer
        // the more efficient Remove method will be called in this case.
        void DeleteEntry(Address start, Address end = kNullAddress)
        {
            // Deletions coming from the GC are directly deleted from the remembered
            // set. Deletions coming from the runtime are added to the store buffer
            // to allow concurrent processing.
            deletion_callback(this, start, end);
        }

        void SetMode(StoreBufferMode mode);

        // Used by the concurrent processing thread to transfer entries from the
        // store buffer to the remembered set.
        void ConcurrentlyProcessStoreBuffer();

        bool Empty()
        {
            for (int i = 0; i < kStoreBuffers; i++) {
                if (lazy_top_[i]) {
                    return false;
                }
            }
            return top_ == start_[current_];
        }

        Heap* heap() { return heap_; }

    private:
        // There are two store buffers. If one store buffer fills up, the main thread
        // publishes the top pointer of the store buffer that needs processing in its
        // global lazy_top_ field. After that it start the concurrent processing
        // thread. The concurrent processing thread uses the pointer in lazy_top_.
        // It will grab the given mutex and transfer its entries to the remembered
        // set. If the concurrent thread does not make progress, the main thread will
        // perform the work.
        // Important: there is an ordering constrained. The store buffer with the
        // older entries has to be processed first.
        class Task : public CancelableTask {
        public:
            Task(Isolate* isolate, StoreBuffer* store_buffer)
                : CancelableTask(isolate)
                , store_buffer_(store_buffer)
                , tracer_(isolate->heap()->tracer())
            {
            }
            ~Task() override = default;

        private:
            void RunInternal() override
            {
                TRACE_BACKGROUND_GC(tracer_,
                    GCTracer::BackgroundScope::BACKGROUND_STORE_BUFFER);
                store_buffer_->ConcurrentlyProcessStoreBuffer();
            }
            StoreBuffer* store_buffer_;
            GCTracer* tracer_;
            DISALLOW_COPY_AND_ASSIGN(Task);
        };

        StoreBufferMode mode() const { return mode_; }

        void FlipStoreBuffers();

        Heap* heap_;

        Address* top_;

        // The start and the limit of the buffer that contains store slots
        // added from the generated code. We have two chunks of store buffers.
        // Whenever one fills up, we notify a concurrent processing thread and
        // use the other empty one in the meantime.
        Address* start_[kStoreBuffers];
        Address* limit_[kStoreBuffers];

        // At most one lazy_top_ pointer is set at any time.
        Address* lazy_top_[kStoreBuffers];
        base::Mutex mutex_;

        // We only want to have at most one concurrent processing tas running.
        bool task_running_;

        // Points to the current buffer in use.
        int current_;

        // During GC, entries are directly added to the remembered set without
        // going through the store buffer. This is signaled by a special
        // IN_GC mode.
        StoreBufferMode mode_;

        VirtualMemory virtual_memory_;

        // Callbacks are more efficient than reading out the gc state for every
        // store buffer operation.
        void (*insertion_callback)(StoreBuffer*, Address);
        void (*deletion_callback)(StoreBuffer*, Address, Address);
    };

} // namespace internal
} // namespace v8

#endif // V8_HEAP_STORE_BUFFER_H_
